لیست الگوریتم های مرتب سازی
در جدول زیر n
تعداد رکرد هایی است که می خواهیم مرتب کنیم و k
شمار کلید های مشخص می باشد. CMP مشخص می کند که
این روش جزء سورت
مقایسه ای هست یا نه. برای برسی دقیقتر هر روش می توانید بر روی نام آن
کلیک کنید.
| نام روش |
بهترین
حالت |
حالت
میانی |
بدترین
حالت |
حافظه |
استحکام |
Cmp |
متد |
نکات
اضافی |
|
حبابی |
O(n) |
— |
O(n2) |
O(1) |
Yes |
Yes |
Exchanging |
Times are for best variant |
|
نوشابه
ای |
O(n) |
— |
O(n2) |
O(1) |
Yes |
Yes |
Exchanging |
|
|
شانه ای |
O(n log n) |
— |
O(n log n) |
O(1) |
No |
Yes |
Exchanging |
|
|
کوتوله ای |
O(n) |
— |
O(n2) |
O(1) |
Yes |
Yes |
Exchanging |
|
|
انتخابی |
O(n2) |
O(n2) |
O(n2) |
O(1) |
No |
Yes |
Selection |
|
|
درجی |
O(n) |
— |
O(n2) |
O(1) |
Yes |
Yes |
Insertion |
|
|
پوسته ای |
O(nlog(n)) |
— |
O(nlog2(n)) |
O(1) |
No |
Yes |
Insertion |
Times are for best variant |
|
درخت
دو دویی |
O(nlog(n)) |
— |
O(nlog(n)) |
O(1) |
Yes |
Yes |
Insertion |
|
|
کتابخانه
ای |
O(n) |
O(nlog(n)) |
O(n2) |
(1+ε)n |
Yes |
Yes |
Inserting |
|
|
ادغامی |
O(nlog(n)) |
— |
O(nlog(n)) |
O(n) |
Yes |
Yes |
Merging |
|
|
ادغامی
درجا |
O(nlog(n)) |
— |
O(nlog(n)) |
O(1) |
Yes |
Yes |
Merging |
Times are for best variant |
|
هیپ |
O(nlog(n)) |
— |
O(nlog(n)) |
O(1) |
No |
Yes |
Selection |
|
|
هموار |
O(n) |
— |
O(nlog(n)) |
O(1) |
No |
Yes |
Selection |
|
|
سریع |
O(nlog(n)) |
O(nlog(n)) |
O(n2) |
O(log n) |
No |
Yes |
Partitioning |
Naive variants use O(n) space |
|
درونی |
O(nlog(n)) |
O(nlog(n)) |
O(nlog(n)) |
O(log n) |
No |
Yes |
Hybrid |
|
|
طبقه
ای |
O(n+k) |
— |
O(n+k) |
O(k) |
Yes |
No |
Indexing |
|
|
سطلی |
O(n) |
O(n) |
O(n2) |
O(k) |
Yes |
No |
Indexing |
|
|
شمارشی |
O(n+k) |
— |
O(n+k) |
O(n+k) |
Yes |
No |
Indexing |
|
|
پایه ای |
O(nk) |
— |
O(nk) |
O(n) |
Yes |
No |
Indexing |
|
|
صبور |
O(n) |
— |
O(nlog(n)) |
O(n) |
No |
Yes |
Insertion |
|
در زیر نیز برخی روش های غیر
عملی که فوق العاده اجرای ضعیفی دارند و به سخت افزار های خاصی احتیاج دارند را
معرفی می کنیم.
|
نام روش |
بهترین حالت |
حالت میانی |
بدترین حالت |
حافظه |
استحکام |
Cmp |
توضیحات
اضافی |
| Bogosort |
O(n) |
O(n × n!) |
unbounded |
O(1) |
No |
Yes |
|
|
احمق |
O(n) |
— |
O(n3) |
O(1) |
Yes |
Yes |
Memory is O(n2) for the recursive
version |
|
دلقک |
O(n2.71) |
— |
O(n2.71) |
O(1) |
No |
Yes |
|
|
مهره ای |
O(n) |
— |
O(n) |
— |
N/A |
No |
Requires specialized hardware |
|
کلوچه
ای |
O(n) |
— |
O(n) |
— |
No |
Yes |
Requires specialized hardware |
|
شبکه
ای |
O(log n) |
— |
O(log n) |
— |
Yes |
Yes |
Requires a custom circuit of size
O(nlogn) |
|
